package leetcode100

// TODO 贪心算法 [经典] 【-】 跳跃游戏
// TODO

func canJump(nums []int) bool {
	// 贪心算法
	// cover表示覆盖下标
	cover := 0
	if len(nums) == 1 {
		return true
	}
	// 从0开始
	for i := 0; i <= cover; i++ {
		// cover 每次应该在原 cover 和当前的 i+nums[i] 取大值，表示覆盖下标
		// i+nums[i]: 下标 i 能跳到的最远位置; 每个节点都有自己能跳到的最原位置
		cover = max3(cover, i+nums[i])
		// 如果覆盖下标能走到最后一个元素，就可以返回true了
		if cover >= len(nums)-1 {
			return true
		}
	}

	// 下标都走完了，cover依然不能走到最后一个元素，肯定false
	return false
}

func max3(a, b int) int {
	if a > b {
		return a
	}
	return b
}
